class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(auto x:stones)sum+=x;
        int n=stones.size(),m=sum/2;
        vector<int> dp(m+1);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=stones[i-1];j--)
                dp[j]=max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
        return sum-2*dp[m];
    }
};
